#
# @lc app=leetcode.cn id=2748 lang=python3
#
# [2748] 美丽下标对的数目
#

# @lc code=start
from math import gcd
from typing import List


class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        ans = 0
        cnt = [0] * 10 #最高位出现的次数
        for x in nums:
            for j in range(1,10):
                if cnt[j] and gcd(j, x%10) == 1: #枚举最高位，看是否有符合条件的
                    ans += cnt[j]
            while x >= 10:
                x //= 10
            cnt[x] += 1
        return ans
# @lc code=end

